1. Field of the Invention
The present invention relates to a method and an apparatus for generating error correction data. The invention also relates to a computer-readable recording medium recording an error correction data generating program thereon. The invention relates particularly to a technique suitable for use in increasing resistance to errors in data transmission, such as streaming data transmission over a communication network (the Internet or the like) in which packet loss frequently occurs.
2. Description of the Related Art
Recently, there have been demands for data communication, such as video data communication and audio data communication, which is performed via various types of communication means such as the Internet. In particular, as a recent data communication service, streaming data distribution on the Internet has been increasingly used. In the streaming distribution, while data is being transmitted from an MPEG (Motion Picture Experts Group) encoder apparatus (hereinafter will be simply called the “encoder”) to an MPEG decoder apparatus (hereinafter will be simply called the “decoder”), received data is replayed in real time. Examples of such data streaming transmission-employed systems are VOD (Video On Demand) systems, streaming distribution systems which distribute live videos, and videoconference systems.
The RTP (Real-time Transport Protocol) [see the following non-patent document 1 (IETF RFC1889)] is one of the Internet technologies which are suitable for use in such real-time communication. In RTP data communications, packets are given time stamps as time information. The time stamp is used by an encoder apparatus on the packet sender end and a decoder apparatus on the packet receiver end to acknowledge the time relationship, whereby the decoder apparatus is capable of performing synchronous replay, without being affected by delay in packet transmission or jitter. However, since RTP does not guarantee real-time data communication, there is a possibility that distribution delay and packet loss occurs in RTP packet transmission.
However, under such a state, the decoder apparatus is still capable of replaying data by using packets that have arrived during an expected time duration. Even if some data loss (packet loss) occurs in video data and audio data, it is still possible to perform low-quality replay of the data or to perform data replay while adding some data correction. In such a case, packets transmitted after some delay or packets in which an error occurs are discarded on the decoder apparatus. That is, even when high-quality data distribution processing is performed, if packet loss or an error occurs, data cannot be replayed in high quality on the decoder apparatus.
As a procedure for solving such a problem of RTP data transmission, TCP (Transmission Control Protocol), which is reliable in data transmission, is used for realizing issuance of packet retransmission requests and retransmission of the requested packets. However, although TCP is efficient in error correction, it has problems of low throughput and large delay. Hence, if the requested packets are retransmitted, it is probable that the packets cannot reach the destination in time. Accordingly, the use of TCP is not sufficient to realize a real-time communication system.
Further, as an error correction method which copes with the packet loss problem, the technique of FEC [Forward Error Correction; see the following non-patent document 2 (IETF RFC2733)] has been developed. FIG. 8 illustrates the FEC error correction method. As shown in FIG. 8, in FEC, a redundant packet (parity) P1, which is error correction data generated on the encoder apparatus 100 using exclusive-OR (XOR) operation, is transmitted together with transmission data (packets) D1 and D2. If a packet is lost over the network 300, in this case the Internet, the decoder apparatus 200 is capable of restoring the lost packet, D1 or D2, so that the lost packet need not be retransmitted from the encoder apparatus 100.
In this manner, FEC provides a reliable media transmission with high interactivity even in network circumstances, such as the Internet, in which packet loss can frequently occur, thereby realizing a service such as the Internet live broadcast. However, in network circumstances in which packet loss bursts appear, it is difficult to provide high-quality media transmission.
Against such a backdrop, the technique of ARQ (Automatic Repeat Request) is developed to cope with such packet loss bursts. FIG. 9 illustrates the ARQ error correction method. As shown in FIG. 9, in ARQ, if a packet loss is detected on decoder apparatus 500, a retransmission request for the lost packet is transmitted to encoder apparatus 400 (see arrow 600), and the encoder apparatus 400 resends the lost packet (see arrow 700).
In the previous systems, either of the FEC technique and the ARQ technique is normally used without switching therebetween. For example, the FEC technique is effective in network circumstances where the transmission rate is low and the error rate is high. On the other hand, in network circumstances where the transmission rate is high and the error rate is low, FEC packet overhead is increased, thereby affecting the transmission efficiency. In contrast to this, the ARQ technique is effective in network circumstances where the transmission rate is high and the error rate is low. On the other hand, in network circumstances where the transmission rate is low and the error rate is high, data exchange relating to packet retransmission is increased, so that the transmission efficiency is affected.
Against such backdrops, techniques in which the ARQ technique and the FEC technique are combined have been developed. For example, the following patent application 1 (Japanese Patent Application Publication No. 2002-9883) and patent application 2 (Japanese Patent Application Publication No. HEI 7-67175) are examples of such techniques.
Patent Application 1 discloses a technique of automatically switching error correction methods by using specific parameters (error rate and transmission rate) to correct errors due to communication data transmission error which occurs over communication network systems. More specifically, received data is decoded to calculate the parameters (error rate/transmission rate), and if the parameters do not exceed their threshold values, the ARQ technique is automatically selected. On the other hand, if the parameters exceed the threshold values, the FEC is automatically selected. With this arrangement, according to the state of the data transmission rate and the transmission efficiency, the most efficient error correction method is automatically selected, and network traffic load can be decreased (see paragraph 0021 through 0023 of Patent Application 1).
Patent application 2 provides a data transmission technique that is most efficient in transmission, by changing the transmission rate according to the line condition of a radio communication division that is not always stable, thereby selecting either or both of the FEC and ARQ techniques. For realizing this, the technique monitors the line condition (error occurrence condition) of the radio communication division, and the transmission rate is varied depending on the error occurrence condition, and either of the ARQ and FEC techniques is selected/decided as an error control method to be applied.
More precisely, if the transmission rate is 9600 bps, the ARQ is employed. If the transmission rate is 4800 bps or 2400 bps, whether correction by the FEC technique is available is evaluated. If the correction is available, self correction is performed. If the correction is unavailable where the transmission rate is 4800 bps, an ARQ retransmission request is issued. In addition, the number of times the retransmission is performed is monitored, and if the number is large, which means line quality is low, the transmission rate is decreased to 4800 bps, and the ARQ and FEC techniques are concurrently used. When the transmission rate is 4800 bps, if the number of times the retransmission is performed is increased, which means line quality is further decreased, the transmission rate is decreased to 2400 bps, and the FEC mode is selected (see paragraph 0014 and 0015 of Patent Application 2).
In the technique of Patent Application 2, control methods appropriate for the data transmission rate and the transmission rate are selected according to the line condition, so that the most efficient transmission rate can be selected.
[Patent Application 1] Japanese Patent Application Publication No. 2002-9883
[Patent Application 2] Japanese Patent Application Publication No. HEI 7-67175
[Non-Patent Document 1] H. Schulzrinne, et al., “RTP: A Transport Protocol for Real-Time Applications”, Request for Comments: 1889, [online], January, 1996, IETF Network Working Group, [retrieved on Aug. 25, 2004], the Internet <URL: http://www.ietf.org/rfc/rfc1889.txt>
[Non-Patent Document 2] J. Rosenberg, et al., “An RTP Payload Format for Generic forward Error Correction”, Request for comments: 2733, [online], December, 1999, IETF Network Working Group, [retrieved on Aug. 25, 2004], the Internet <URL: http://www.ietf.org/rfc/rfc2733.txt>
The previous systems have the following problems. Although the previous techniques are capable of performing efficient error correction with a single encoder and a single decoder being employed, the systems do not pay consideration to systems where a single encoder distributes video data to two or more decoders.
That is, provided that intervals at which redundant packets are inserted are the same among all of the decoders, and that all the decoders belong to the same network, and that the number of times a retransmission request is transmitted is almost equal among the decoders, error correction and suppression of fluctuation of the data transmission band are realized as efficiently as the system in which only one encoder and one decoder are employed. However, provided that some or all of the decoders belong to different networks, and that the quality of one of the networks is low so that the number of retransmission requests issued by a decoder belonging to the low-quality network is particularly increased, the data transmission band for the decoder is increased, thereby affecting the band of the network.
Further, provided that the redundant packet insertion intervals differ among the decoders, depending on the quality of the networks to which the decoders belong, the encoder needs to generate (exclusive-OR operation) different redundant packets for different decoders, so that load on the encoder is increased.
Here, it is conceivable to insert redundant packets at the same intervals for all of the decoders. At this time, the interval is adjusted to one decoder in which errors occur most frequently. In that case, redundant packets are inserted at long intervals for the other decoders in spite of the fact that errors occur less frequently in the transmission data sent to these decoders. It is sometimes considered that such increased redundant packet insertion intervals would cause no problem because errors rarely occur. However, since the FEC technique is forward prediction, which has a strong preventative aspect against errors, the FEC technique cannot cope with suddenly increased loss which can be caused at some timings.
Further, if the insertion interval of redundant packets for other decoders is changed so as to agree with the insertion interval of a specific decoder, not only load on the encoders is increased, but also the insertion intervals for those decoders are changed, so that desired error correction is unavailable. In addition, the change in insertion intervals of the redundant packets will change the transmission rate, so that another communication system (TCP, etc.) in the network begins using that band, thereby reducing the usable bands for streaming. The necessary band is thus preferably used all the time.